import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //01背包
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //创建dp表
        int[][] dp1 = new int[n + 1][V + 1];
        int ret = 0;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp1[i][j] = dp1[i - 1][j];
                if(j - v[i] >= 0) dp1[i][j] = Math.max(dp1[i][j],
                        dp1[i - 1][j - v[i]] + w[i]);
                ret = Math.max(ret, dp1[i][j]);
            }
        }
        System.out.println(ret);

        //创建dp表
        int[][] dp2 = new int[n + 1][V + 1];
        int ret2 = -1;
        //初始化
        for(int j = 1; j <= V; j++){
            dp2[0][j] = -1;
        }
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp2[i][j] = dp2[i - 1][j];
                if((j - v[i] >= 0 && dp2[i - 1][j - v[i]] != -1))
                    dp2[i][j] = Math.max(dp2[i][j], dp2[i - 1][j - v[i]] + w[i]);
            }
        }
        ret2 = dp2[n][V];
        if(ret2 < 0) ret2 = 0;
        System.out.println((ret2));
    }

    //01背包(优化)
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //创建dp表
        int[] dp = new int[V + 1];
        int ret = 0;
        //填表
        for(int i = 0; i <= n; i++){
            for(int j = V; j >= 0; j--){
                if(j - v[i] >= 0) dp[j] = Math.max(dp[j],
                        dp[j - v[i]] + w[i]);
                ret = Math.max(ret, dp[j]);
            }
        }

        System.out.println(ret);

        //创建dp表
        int[] dp2 = new int[V + 1];
        int ret2 = -1;
        //初始化
        for(int j = 1; j <= V; j++){
            dp2[j] = -1;
        }
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = V; j >= 0; j--){
                if((j - v[i] >= 0 && dp2[j - v[i]] != -1))
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
            }
        }
        ret2 = dp2[V];
        if(ret2 < 0) ret2 = 0;
        System.out.println((ret2));
    }

    //分割等和子集
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        //创建dp表
        boolean[][] dp = new boolean[n + 1][sum / 2 + 1];
        //初始化
        for(int i = 0; i <= n; i++) dp[i][0] = true;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= sum / 2; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - nums[i- 1] >= 0) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
        //返回
        return dp[n][sum / 2];
    }

    //分割等和子集(空间优化)
    public boolean canPartition2(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        //创建dp表
        boolean[] dp = new boolean[sum / 2 + 1];
        //初始化
        //for(int i = 0; i <= n; i++) dp[i][0] = true;
        dp[0] = true;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = sum / 2; j >= 0; j--){
                if(j - nums[i- 1] >= 0) dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        //返回
        return dp[sum / 2];
    }
}